The invention relates to a method of computer calculations that avoids round off errosion. It further relates to optimizing noise processing operations, such as spectral analysis, filtering, cancellation, in telecommunications, medical or instrumentation systems. It performs the usual arithmetic (+/*xe2x88x92) and transcendental/trigonometric operations on floating point numbers, the most prevalent representation of real numbers on diverse computer architectures. These properties stem directly from the behavior of the D Scale.
Digital numerical calculation involves round off errors that accumulate when repetitive operations are performed. Where a limited number of calculations are involved, the calculation may be carried out to 16 significant digits and results displayed to 12 digits. However, where billions of calculations are performed, this may be insufficient. It is also known that single non linear model sof physical systems create such problems and may appear to be chaotic, thereby limiting the ability to forecast.
Current State-of-the-Art
Review of Current Floating Point Computer Arithmetic
The mathematical foundation of computer arithmetic is Boolean algebra. This is a self-consistent set of rules specifying the results (or mappings) of logical operations on bits. A bit is the basic unit of computation having values of 0 or 1 (i.e, true or false). The rules are often implemented, or regarded, as logical truth tables. These operations also have corresponding counterparts in the mathematical theory of sets (e.g., union corresponding to + and intersection corresponding to *). Such operations include negation and basic arithmetic (addition, subtraction, multiplication, division).
From that foundation, many approaches evolved to perform calculations on groups of bits, in the form of real numbers. A real number is either rational, expressible as a fraction, or irrational. And a real number is represented in a computer as a sequence of 0/1 bits. Many algorithms are used to perform the calculations or computations on these blocks of bits.
Out of the many arithmetic techniques that evolved over the years, floating point arithmetic emerged as the clear winner. Therefore, this presentation will focus exclusively on floating point computations as the benchmark from which to measure the merits of the D Arithmetic. The integer arithmetic will also be mentioned because of its frequent use in real-time calculations.
A floating point number is conveniently expressed in scientific notation, having three components. They are the sign, the mantissa, and the power [not correct term]. Or, in the usual base 10 notation:
x=0.n1 . . . ns*10s
s indicates the number of significant digits. A significant digit is one that has physical significance because it was actually measured during sampling.
Over the years, standard packaging of real numbers evolved to improve computational efficiency. These special packaging are referred to as xe2x80x9cdata typesxe2x80x9d.
There is also an xe2x80x9cinfinite precisionxe2x80x9d number which uses so many bits to represent a real number, that the precision is effectively xe2x80x9cinfinitexe2x80x9d. Then the round-off errors effectively disappear, to provide the truest representation of multiple calculations on measured numbers. Until recent advances in computer CPU processing speed and memory capacity/price, it was not commercially feasible to work with infinite precision numbers. They require much more memory and processing time to implement, vis-a-vis the native data types.
Over time, the native data types were considered the golden compromise between the conflicting constraints of calculation efficiency vs. accuracy. But infinite precision numbers were increasingly used for more exacting calculations in scientific and even in financial applications. Indeed, packaging of indefinite and otherwise custom precision numbers is occurring more frequently. For example, the Java language packaged an infinite precision arithmetic in its Big Decimal object. Another commercial example is the packaging of a Money object to precisely handle arithmetic on currency sub-units (like cents).
Infinite precision arithmetic also serves as a useful benchmark against which the other restricted precision calculations can be compared. Because the infinite precision calculations do not have inherent rounding errors, they provide true values.
The following floating point representation will be used to show how the current standard floating point arithmetic can destabilize. A xe2x80x9cdoublexe2x80x9d data type is indicated, resulting from n calculations. In scientific notation, it is:
0.n1 . . . ns . . . nb . . . nc*10s
Here, s again indicates the number of significant digits maintained from the actual original data measured. The first s digits are significant. The digits from s+1 until b are the buffer zone that will absorb the effect of round-off, errors. This buffer, in effect, shields the significant digits from the ripple effect of round-off. The digits from b+1 until c are the digits already corrupted by the rippling effect of previous round-off operations.
Note that the round-off error is generally indeterminate, and not calculable to a definite value. That increases, yet further, the uncertainty in the resultant calculations.
Numerical Instability of Floating Point Calculations
One problem is the inherent instability of the arithmetic due to the ever presence of rounding errors. Indeed, it does not even obey the basic laws of algebra, such as the associative law. That is, if A, B, C are floating point representations of real numbers, then it is not guaranteed that (A*B)*C=A*(B*C). These rounding errors accumulate until the significant digits are corrupted by the rippling round-off errors. Thus, the floating point arithmetic can only be useful for repeated calculations on a limited number of sample points, after which instability sets in.
The numerical stability can be vividly illustrated by following these two sets of (* or +) calculations on the same sequence of real numbers. Each number is expressed in scientific notation, with the significant, buffer and corrupted (or rounded) digits indicated, as described in the previous section.
The first set of calculations is performed on the standard xe2x80x9cdoublexe2x80x9d representation. And the second set is performed on the infinite precision representation. The second sequence serves as a genuine benchmark against which the double precision calculations are compared, because it does not have inherent rounding errors.
Both traces start with the same digit, having s1 significant digits and a buffer of b1 digits. The first case already starts with a corrupted digit because of the round-off at its end. The second number does not have a round-off error because of its infinite precision.
Standard type (double) xe2x80x9cInfinitexe2x80x9d Precision                                           0.            ⁢                          n              l1                        ⁢                          xe2x80x83                        ⁢            …            ⁢                          xe2x80x83                        ⁢                          n              s1                        ⁢                          xe2x80x83                        ⁢            …            ⁢                          xe2x80x83                        ⁢                          n              b1                        ⁢                          xe2x80x83                        ⁢            …            ⁢                          xe2x80x83                        ⁢                          n              c1                        *                          10              s                                                                        *                          /              +                                                                        *                          /              +                                                                        0.            ⁢                          n              lk                        ⁢                          xe2x80x83                        ⁢            …            ⁢                          xe2x80x83                        ⁢                          n              sk                        ⁢                          xe2x80x83                        ⁢            …            ⁢                          xe2x80x83                        ⁢                          n              bk                        ⁢                          xe2x80x83                        ⁢            …            ⁢                          xe2x80x83                        ⁢                          n              ck                        *                          10              s                                            ⁢          xe2x80x83        ⁢                                        0.            ⁢                          n              l1                        ⁢                          xe2x80x83                        ⁢            …            ⁢                          xe2x80x83                        ⁢                          n              s1                        ⁢                          xe2x80x83                        ⁢            …            ⁢                          xe2x80x83                        ⁢                          n              b1                        ⁢                          xe2x80x83                        ⁢            …            *                          10              s                                                                                      *                              /                +                                      ,                                                                          *                              /                +                                      ,                                                            0.            ⁢                          n              lk                        ⁢                          xe2x80x83                        ⁢            …            ⁢                          xe2x80x83                        ⁢                          n              sk                        ⁢                          xe2x80x83                        ⁢            …            ⁢                          xe2x80x83                        ⁢                          n              bk                        ⁢                          xe2x80x83                        ⁢            …            *                          10              s                                            ⁢      xe2x80x83  
Note at this point, that the buffer digits have become corrupted in the first case.
Subsequent calculations will corrupt the significant digits.                               0.          ⁢                      n            lr                    ⁢                      xe2x80x83                    ⁢          …          ⁢                      xe2x80x83                    ⁢                      n            sr                    ⁢                      xe2x80x83                    ⁢          …          ⁢                      xe2x80x83                    ⁢                      n            cr                    *                      10            s                                                        *                      /            +                                                        *                      /            +                                                        0.          ⁢                      n                          l              ⁢                              xe2x80x83                            ⁢              m                                ⁢                      xe2x80x83                    ⁢          …          ⁢                      xe2x80x83                    ⁢                      n                          c              ⁢                              xe2x80x83                            ⁢              m                                ⁢                      xe2x80x83                    ⁢          …          *                      10            s                                ⁢      xe2x80x83    ⁢                              0.          ⁢                      n            lr                    ⁢                      xe2x80x83                    ⁢          …          ⁢                      xe2x80x83                    ⁢                      n            sr                    ⁢                      xe2x80x83                    ⁢          …          ⁢                      xe2x80x83                    ⁢                      n            br                    ⁢                      xe2x80x83                    ⁢          …          *                      10            s                                                        *                      /            +                                                        *                      /            +                                                        0.          ⁢                      n                          l              ⁢                              xe2x80x83                            ⁢              m                                ⁢                      xe2x80x83                    ⁢          …          ⁢                      xe2x80x83                    ⁢                      n            sm                    ⁢                      xe2x80x83                    ⁢          …          ⁢                      xe2x80x83                    ⁢                      n            bm                    ⁢                      xe2x80x83                    ⁢          …          *                      10            s                              
Note, in the first case, that more digits become corrupted as the number of calculations increase, until the significant digits become meaningless as well. Further, the round-off process typically is not readily quantified for multiple calculations. Therefore, it is not possible to determine how a calculated result compares to its infinite precision counterpart. In a sense, each intermediate result contains the history or memory of its previous calculations through the impact on its buffer bits.
Data Communications Overhead in Microprocessor
There is a second problem with the usual implementations of floating point computer arithmetic, involving the communications costs in moving data in memory to the calculating unit. More specifically, floating point arithmetic implementations generally require the physical movement of data between a computer""s main memory, through a cache, then through CPU registers, and then through an Arithmetic Logic unit (ALU) or the more specialized arithmetic unit needed for transcendental function calculations.
Limited-Portability of Floating Point Arithmetic
A third problem is that floating point calculations are performed somewhat differently across multiple computer architectures, notwithstanding the widespread adherence to the IEEE754 standard. As a result, arithmetic operations on the same sequence of real numbers could produce different results on different computer architectures. Therefore, the arithmetic is not completely portable from one computer manufacturer to another. The problem is most acute with transcendental functions.
Numerical Instability of Standard Floating Point Calculations
Many solutions have been proposed over the years, and several actually used in commercial applications. They generally include, from most to least used:
a. Accept the inherent inaccuracy of floating point calculations. Add buffer bits. Then estimate the number of buffer digits needed to prevent the cumulative rounding errors from corrupting the good, significant digits. For example, one technique is to use the xe2x80x9cdoublexe2x80x9d data type for calculations involving xe2x80x9cfloatxe2x80x9d data type accuracy. Or the Java language""s BigDecimal object is used to conveniently construct numbers with even more digits. Finally, vendors have provided specialized packaging of certain number types like xe2x80x9cMoneyxe2x80x9d [Rogue Wave Software Inc., xe2x80x9cMoney++xe2x80x9d], along with an accompanying algebra to perform meaningful and accurate calculations on those data types.
b. Accept the inherent inaccuracy of floating point calculations. Analyze. Then use numerical analysis techniques to quantify error bounds and to provide guidelines on when the calculations become unstable. This technique tends not to be used because the mathematics involved is not well understood or appreciated by users. Even if understood, it can be difficult to implement the analyses. And the quantitative methods could be time consuming and also not proven in effectiveness.
c. Use new models to drive floating point implementations.
This includes xe2x80x9cinterval analysisxe2x80x9d. Many such solutions have been proposed over the years, and some actually used in specialized, well controlled, situations.
Data Communications Overhead in CPU
ALU units tend to use embedded tables for efficient computations of more complex transcendental basic arithmetic operations.
Non-Portability of Floating Point Calculations
The IEE754 standard specifies how to handle floating point calculations. It is now adhered to by virtually all computer manufacturers. But there is still enough room for interpretation in these standards that different results can still result from executing the same sequence of numbers on different computer architectures.
An alternate approach is to use constructs in a higher level computer language, to blanket over the differences from one architecture to the next. In particular, the Java language might be used for that purpose.
Deficiencies of Existing xe2x80x9cPrior Artxe2x80x9d
Numerical Instability of Floating Point Calculations Numerical instability is still present in industry standard approaches to iterative numeric computations.
Data Communications Overhead in CPU
Even with the use of optimized and tuned embedded CPU components, there is still data movement between memory and CPU. The communications overhead is most pronounced when transcendental calculations are performed.
Non-Portability of Floating Point Calculations
The IEE754 standard has contributed enormously to increasing the portability of floating point computations over many disparate computer architectures. But it still cannot guarantee portability due to flexibility and ambiguity in the interpretation of the standards.
Also, the Java data types still are not as portable as originally intended or expected. An article in EETimes described flaws with Java as a fully portable computation engine.
The invention is a signal and noise processor that employs the D Scale, which has previously been disclosed in patent application Ser. No. 09/326,084 now U.S. Pat. No. 6,477,553 in connection with signal and image processing and modeling. The signal processor employs repetitive calculations based on a D Arithmetic has two components. The first is its set of mappings from each pair of points in a D Scale into a point in a D Scale. For example, D Arithmetic multiplication mappings are created by applying the usual, floating point, multiplication to each pair of points in the cross-product of a D Scale with itself. Then each decimal result is mapped to a point in the same D Scale, using the D Scale mapping algorithm described in Ser. No. 09/326,084, which is included herein by reference. Thus, this algorithm generates a set of pre-assigned, or pre-wired, arithmetic operation mappings (e.g., one for multiplication, another for addition). These mappings are generated once, stored in a computer database or its equivalent (e.g. hard wired into a computer chip), and then used forever onwards. This contrasts with the usual notion of arithmetic xe2x80x9ccalculationsxe2x80x9d whereby an unknown quantity is discovered for each pair of input values by applying Boolean Algebra to the bits comprising the numeric input values.
The second component is an algorithm to map actual, measured values, into D Scale points. The accuracy and usefulness of the D Arithmetic mappings depends on the precision of the D Scale used. A D Arithmetic that was constructed from a high resolution D Scale can more accurately map sampled data with a high number of significant digits. That is, the result of iterative operations will yield a D Scale value that is within a tighter tolerance of the actual value. The minimum resolution of resolution of a D Arithmetic is determined by the reciprocal of the maximum prime number in the D Scale. However, most important, the average resolution can be orders of magnitude higher because of the irregular pattern of points in a D Scale. A tighter variance e resolution is achieved by using more e sub-scales to fill in the D Scale. It amplifies the effect of far fewer sample points to attain the same mean resolution, with a tight variance, as the naxc3xafve, high uniform sampling rate.
The D Arithmetic does not need to use standard Boolean Algebra, which is at the heart of virtually all mainstream commercial arithmetic implementations. Instead, its pre-wired maps embody what standard floating point arithmetic will calculate using Boolean Algebra or whatever operations on a number""s bits. Its pre-wired mappings are most readily envisioned as straightforward tables (e.g., multiplication and trigonometric tables). The implementation of these mappings is commercially attractive because of the ever-expanding memory, CPU and bandwidth resources available. Further, the number of mappings in a D Arithmetic implementation can be adjusted to accommodate the required precision of specific applications. This is especially attractive for embedded systems, where resources are husbanded to the fullest, and where it might not be attractive to pay for extra significant digit precision.
See FIG. 1 Hierarchy of Computer Arithmetic Abstractions
The most useful property of the D Arithmetic is its numeric stability, even as the number of calculations on data set values increases. This contrasts sharply with standard floating point arithmetic techniques, whereby accuracy is rapidly lost due to significant digit erosion from cumulative round-off errors, as the number of calculations increases.
A second property is its portability across diverse computer platforms. That is, the same calculations are guaranteed to produce identical results regardless of computer platform used to actually perform the calculations. This also contrasts with the industry standard arithmetic (although the IEEE754 standard appreciably minimized differences across diverse computing platforms).
The third property is its relative efficiency. Its efficiency derives from its use of pre-calculated table values that are accessed in memory or on a networked node. This avoids the communications overhead in moving data between the CPU arithmetic logic unit (ALU) and memory. Again, this contrasts with standard industry practice whereby data must move around to CPU ALU and back for calculated results. Finally, D Arithmetic results"" deviations or errors are bounded, quantifiable and readily verifiable.
At the heart of the processing is the industry standard calculation of the Discrete Fourier Transform (DFT) of a signal or image using the full set of sampled data points. Typically, 1 dimensional signal sample data is partitioned into smaller subsets, called periodograms, and then stitched together with the aid of xe2x80x9cwindowingxe2x80x9d. And 2 dimensional images are typically partitioned into blocks. Each partition is then used in a DFT calculation to insure that accurate results are still obtainable, before the cumulative round-off overwhelms the original significant digits. For, as the number of data points used in an itterative DFT calculation increases, the likelihood of intermediate calculations being corrupted by round-off errors increases, rendering the final result highly suspicious or completely useless. But this partitioning also has a cost in introducing extra steps to the overall data processing flow. It also requires an extra statistical analysis step to smooth the resulting data. And it introduces artifacts. Indeed, the use of blocks generates visible artifacts in the form of subtle block boundaries across a processed image.
1. Introduction to the D Arithmetic
2. The D Arithmetic
2.1 Commercial Feasibility
2.2 Outline of D Arithmetic Process Flow
2.3 Mapping Actual Measurements into D Scale Points
2.4 Random Mapping to Right/Left D Scale Neighbors
2.5 Construction of Static D Arithmetic Operation Mappings
2.6 Factoring Scaling into D Arithmetic Mappings
2.7 Proof of Accuracy and Stability of D Arithmetic Operations
2.8 D Arithmetic Big Numbers
2.9 D Arithmetic for Transcendental/Trigonometric Functions
3. Validating the D Arithmetic
4. Sensitivity of D Arithmetic to Random Number Generators
5. Implementing the D Arithmetic
6. Benefits of D Arithmetic/D Scale to Process Noisy Data
7. Commercial Noise Processing Applications of the D Arithmetic/D Scale
8. Other Commercial Applications of the D Arithmetic
10. Example of Construction of a D Arithmetic
11. Examples of D Arithmetic Applications References